package com.gorkr.dp;

import java.util.Arrays;

/**
 * @author gorkr
 * @date 2022/06/18 10:51
 **/
public class H1312MinimumInsertionStepsToMakeAStringPalindrome {

    //
    public int minInsertions(String s) {
        // dp 定义  dp[i][j] 是 s[i...j]成为回文串的最少操作次数
        int[][] dp = new int[s.length()][s.length()];

        // base case
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = 0;
            // 忘i>j时均为0
        }

        // 状态转移
        for (int i = s.length()-2; i>=0; i--) {
            for (int j = i+1; j <s.length() ; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i][j-1],dp[i+1][j])+1;
                }
            }
        }
        return dp[0][s.length()-1];
    }


}
    